#include<iostream>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<math.h>
#include<assert.h>
#include<stack>
#include<vector>
#include<set>
#include<unordered_map>
using namespace std;
template<class k,class v>
class avltreenode
{
public:
    pair<k, v> _kv;
    avltreenode* _left;
    avltreenode* _right;
    avltreenode* _parent;
    int _bf;
    avltreenode(const pair<k,v>& kv):
        _kv(kv),
        _left(nullptr),
        _right(nullptr),
        _parent(nullptr),
        _bf(0)
    {}
    
};
template <class k,class v>
class avltree
{
public:
    typedef avltreenode<k,v> node;
    bool insert(const pair<k,v>& kv)
    {
        node* newnode = new node(kv);
        if (_root == nullptr) {
            _root = newnode;
            return true;
        }
        node* parent = nullptr;
        node* cur = _root;
        while (cur) 
        {
            if (cur->_kv.first > kv.first) 
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first) 
            {
                parent = cur;
                cur = cur->_right;
            }
            else return false;
        }
        if (parent->_kv.first > kv.first)
            parent->_left = newnode;
        else
            parent->_right = newnode;
        newnode->_parent = parent;

        cur = newnode;
        //接下来进行更新平衡因子
        while (parent != nullptr)
        {
            if (cur == parent->_right)
                parent->_bf++;
            else parent->_bf--;
            if (parent->_bf == 0)
                break;
            else if (parent->_bf == 1 || parent->_bf == -1)
            { 
                cur = parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)//需要旋转，旋转之后子树的高度跟原来插入时子树的高度是相同的
            {
                if (parent->_bf == -2 && parent->_left->_bf == -1)
                    RotateR(parent);
                else if (parent->_bf == 2 && parent->_right->_bf == 1)
                    RotateL(parent);
                else if (parent->_bf == -2 && parent->_left->_bf == 1)//左右双旋
                    RotateLR(parent);
                else if (parent->_bf == 2 && parent->_right->_bf == -1)
                    RotateRL(parent);
                else assert(false);
                break;
            }
            else assert(false);
        }
        return true;
    }
    void inorder()//中序遍历，关于树的很多函数都是要求从树的根部开始，但是根是私有的，在外面无法访问，所以可以套两层，这就是内层
    {
        inorder(_root);
    }
private:
    void inorder(node* cur)//中序遍历，关于树的很多函数都是要求从树的根部开始，但是根是私有的，在外面无法访问，所以可以套两层，这就是内层
    {
        if (cur == nullptr) return;
        inorder(cur->_left);             // 先递归遍历左子树
        cout << cur->_kv.first << ':' << cur->_kv.second << endl;       // 再输出当前节点值
        inorder(cur->_right);            // 最后递归遍历右子树
    }
    node* _root=nullptr;
    void RotateR(node* parent)
    {
        node* subL = parent->_left;
        node* subLR = subL->_right;

        subL->_right = parent;//先改变subL相应的指针
        subL->_parent = parent->_parent;

        if (parent == _root) _root = subL;
        else
        {
            if (parent->_parent->_left == parent)//改parent->_parent得到指针
                parent->_parent->_left = subL;
            else parent->_parent->_right = subL;
        }

        parent->_parent = subL;//再改parent相应的指针
        parent->_left = subLR;

        if (subLR) subLR->_parent = parent;//修改subLR的指针

        parent->_bf = 0;//修改平衡因子
        subL->_bf = 0;
    }
    // 调整后的左旋函数
    void RotateL(node* parent)
    {
        node* subR = parent->_right;
        node* subRL = subR->_left;

        //修改subR的相关指针
        subR->_parent = parent->_parent;
        subR->_left = parent;

        if (parent == _root) _root = subR;
        else
        {
            if (parent->_parent->_left == parent)
                parent->_parent->_left = subR;
            else parent->_parent->_right = subR;
        }

        if (subRL) subRL->_parent = parent;//修改subRL的相关指针

        parent->_right = subRL;//修改parent相应的指针
        parent->_parent = subR;//注意这里修改了parent的parent，因为原parent的parent也有指针需要修改，所以要么用变量记录一下，要么将paarent的parent的修改放到后面

        subR->_bf = 0;
        parent->_bf = 0;
    }
    void RotateLR(node* parent)
    {
        node* subl = parent->_left;
        node* sublr = subl->_right;
        int bf = sublr->_bf;
        RotateL(subl);
        RotateR(parent);
        if (bf == -1)
        {
            subl->_bf = 0;
            parent->_bf = 1;
        }
        else if (bf == 1)
        {
            subl->_bf = -1;
            parent->_bf = 0;
        }
        else
        {
            subl->_bf = 0;
            parent->_bf = 0;
        }
        sublr->_bf = 0;
    }
    void RotateRL(node* parent)
    {
        node* subr = parent->_right;
        node* subrl = subr->_left;
        int bf = subrl->_bf;
        RotateR(subr);
        RotateL(parent);
        if (bf == -1)
        {
            subr->_bf = 1;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            subr->_bf = 0;
            parent->_bf = -1;
        }
        else
        {
            subr->_bf = 0;
            parent->_bf = 0;
        }
        subrl->_bf = 0;
    }
};

int main()
{
    avltree<int, int> avl1;
    int ch[] = { 4,2,6,1,3,5,15,7,16,14 };
    for (int e:ch)
        avl1.insert({ e,e });
    avl1.inorder();
    return 0;
}